/**
 * Created by jack on 18/3/30.
 */
class MinPath {
    private int height = 0;
    private int width = 0;
    private int[][] grid;
    public int minPathSum(int[][] grid) {
        this.grid = grid;
        height = grid.length;
        if(height == 0){
            return 0;
        }
        width = grid[0].length;
        if(width ==0){
            return 0;
        }
        int step = 0;
        int maxstep = height + width ;
        int basey = 0;
        int basex = 0;
        int y,x;

        while(step < maxstep){
            step ++;
            if(step <= height){
                x = basex;y = basey;
                while(x < width && y >=0){
                    grid[y][x] += getsmaller(y,x);
                    x ++;
                    y --;
                }
                basey ++;
            }else{
                basex ++;
                x = basex;
                y = basey - 1;
                while(x < width && y >= 0){
                    grid[y][x] += getsmaller(y,x);
                    x ++;
                    y --;
                }
            }
        }
        return grid[height -1][width -1];
    }

    /**
     * 获取到较小的前驱step
     * @return 较小的那个前驱step的值
     */
    private int getsmaller(int y,int x){
        if(y == 0 && x == 0){
            return 0;
        }
        if(y == 0){
            return grid[y][x-1];
        }
        if(x == 0){
            return grid[y-1][x];
        }
        return Math.min(grid[y][x-1],grid[y-1][x]);
    }

    public static void main(String[] args) {
        int [][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        int a = new MinPath().minPathSum(grid);
        System.out.println(a);
    }
}